Graph M-Coloring Challenge
Given a graph (represented by an adjacency matrix) and a number of available colors ($m$), the task is to find a way to color all vertices such that **no two adjacent vertices share the same color**.
Input and Output Format
- **Input:** Adjacency matrix (V x V) followed by the number of colors ($m$).
- **Output:** A space-separated list of the assigned colors for each vertex (1 to $V$), or the string "Solution does not exist".
Sample Input/Output
Sample 1 (Success):
4
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
3
Output:
1 2 3 2
Sample 3 (Failure):
4
0 1 0 1
1 0 0 1
0 0 0 0
1 1 0 0
2
Output:
Solution does not exist
Backtracking for M-Coloring
The Graph M-Coloring problem is solved by using **Backtracking**, a systematic search technique that explores the solution space tree. The algorithm attempts to color vertices one by one (from vertex 0 to $V-1$).
Core Logic
- **State:** The current vertex being colored (k) and the current color assignment array.
- **Decision:** For the current vertex $k$, try all available colors $c = 1$ to $m$.
- **Constraint Check (Is Safe?):** A color $c$ is valid for vertex $k$ only if none of its adjacent neighbors have already been assigned color $c$.
- **Recurse & Backtrack:** If a color is safe, assign it, and recursively move to $k+1$. If the recursive call fails, **un-assign** the color (backtrack) and try the next color.
Base Cases
- **Success:** If all vertices ($k = V$) have been successfully colored, return `true`.
- **Failure:** If no valid color can be assigned to the current vertex $k$ after trying all $m$ colors, return `false`.
Dynamic Execution Trace
Enter input and click "Execute Coloring" to see the full backtracking trace flow here.